\chapter{Traffic Information Propagation in Stationary Sensor Networks}

In this chapter we present our work on data propagation in stationary traffic monitoring sensor networks that have been temporarily deployed. This work corresponds to Scenario 2 that we discussed in Section \ref{sec:scenarios}. Our goal is to minimize communication incurred by the propagation of traffic data from a temporary deployment of stationary sensors to the Traffic Monitoring Centre gateways. Such a temporary deployment is meant to support the second class of applications we are considering, those utilized for future planning decisions by local authorities. Since this class of applications does not require the most recent traffic information about the network, we are focusing on periodic traffic data propagation with a report period that is much larger than the sensing period. 

\section{Assumptions}
\subsection{Architecture}
\label{sec:sensarch}
We assume a network architecture that includes two types of nodes: sensor nodes and gateway nodes. Sensor nodes can be equipped with a variety of sensors. In this work we assume sensor nodes are set up to measure traffic flow (cars/time) although this can be easily changed to any other traffic attribute. We assume that sensor nodes communicate over wireless links with neighbouring nodes in their range in order to relay data towards a gateway node. In the temporary deployment we are considering, we expect most, if not all, sensor nodes to be battery powered devices that have limited storage and processing capabilities.

Gateway nodes collect the readings from the sensor nodes. As previously defined in Section \ref{sec:sens}, they have a fixed power source, unlimited bandwidth, storage and processing capabilities, and relay data to the TMC where the traffic monitoring applications are running. We will evaluate the impact of deploying several gateways on the cost of data propagation.

\begin{figure}[htbp]
	\centering
	\psfrag{1km}{1 km}
	\includegraphics[scale=0.4]{dwg/stationary_overview.eps}
	\caption{The scenario we are considering. Circles represent stationary sensors monitoring vehicle flow.}
	\label{figure:cambridge}
\end{figure}

We assume that the network is connected, i.e. every sensor node can forward its data to a gateway node either directly, if the gateway is in its range, or through other sensor nodes over multiple hops. Figure~\ref{figure:cambridge} illustrates our scenario.

Since there is always a connected path from each node to a gateway, we assume that the propagation delay of a message is negligible compared to the report period. We are therefore ommitting the delay clause of the general query that we defined in Section~\ref{sec:objectives}. This work aims to answer queries of the following form:
\begin{verbatim}
  SELECT attribute FROM roadsegments 
  SENSE_EVERY	sensingPeriod
  REPORT_EVERY repPeriod
  REPORT_ACCURACY repError
\end{verbatim}
 

\subsection{Traffic Data Generation}

We have based our analysis on a real traffic dataset generated by an inductive loop deployment in the city of Cambridge. It consists of traffic flow readings provided every 5 minutes for a period of 30 days during May 2006. We therefore assume that each sensor node produces a time series of flow readings with the same frequency: $\verb|sensingPeriod|=5min$


\section{Algorithms}
\label{section:correlations}


Our goal is to devise efficient algorithms to propagate the time series to the gateway and we begin by studying the properties of our urban traffic dataset. We are aiming to identify temporal and spatial redundancy in the flow data. Since our time series measures traffic, we expect to observe a seasonal effect with a period of 24 hours. Indeed, we observed that time series fluctuations follow a daily pattern that is only interrupted during weekends and a more consistent weekly pattern. For our algorithms we decided to focus on the daily rather than the weekly variation for two reasons: 
\begin{itemize}
\item{Propagating data on a weekly basis is more likely to effect the planning application's results than propagating every day; a missing week's flow data may have a noticeable impact.}
\item{In temporary deployments sensor nodes are typically memory-constrained devices.}
\end{itemize}

Thus, we divide flow measurements to derive a time series per day per sensor and set \verb|repPeriod|$=24h$ in our query. For example the tuple $SID, d, [f_1, f_2,\ldots,]$, denotes that sensor $SID$ reported on date $d$ readings $f_1$ in the first five minutes, $f_2$ in the next five minutes, etc. 

We present a class of algorithms for sending periodic traffic updates from the sensor nodes to the gateway nodes that aim at reducing the data to be transmitted. Gateway nodes are placed to minimize the sum of hop counts from sensor nodes to the closest gateway. All algorithms discussed in this section use tree-based routing: each sensor node selects to forward its data hop-by-hop to the closest gateway node, i.e. the one accessible using the least number of hops. It forwards its data to its \emph{parent}, which is the sensor on the min-hop path to the gateway node. Trees that connect sensor nodes to gateway nodes through min-hop paths are generated during an initial network configuration phase using a simple flooding protocol, and they are maintained throughout the network's lifetime. 

Each node locally produces a large time series of traffic data per period, which, if propagated in an uncompressed form, would require a large number of transmissions. Given the user's tolerance for a small error in the reported data, we examine lossy signal compression based on a prominent signal processing technique, the Fast Fourier Transform (FFT), and we evaluate its efficiency in reducing communication.

\begin{figure*}[htbp]
\begin{center}
		\includegraphics[height=1.8in]{dwg/time.eps}
		\caption{Time on a mote.}
		\label{figure:time}
\end{center}
\end{figure*}


We first examine the computation time of FFT on the actual resource-constrained sensor nodes. We implemented it in NesC for TinyOS, and measured its computation time on the Tmote Sky~\cite{moteiv} platform, while varying the length of the input time series. Computation time was measured to be close to linear in the length of the input time-series. Figure~\ref{figure:time} shows the computation time of FFT for time series of variable size, measured on the actual sensor platform. Despite the ($O(n\log{}n)$ complexity of FFT, a sensor node can process the time series of a whole day (24 hours) in just 4.6 seconds of computation. 

After the application of FFT, we compress by retaining only a certain number of Fourier coefficients so that our time series can be approximated with the desired error. Figure~\ref{figure:fouriermse} shows the time series approximation obtained when only the first 15 coefficients are used, which require $n*sizeof(float)$ bytes of memory. The first FFT coefficients correspond to the lower frequencies of the signal which account for the major signal variations. 

\begin{figure*}[htbp]
\begin{center}
		\epsfig{file=dwg/c-flow.eps, height=1.8in}
		\caption{The Fourier approximation of 24 hours of time series data (288 integer flow values). The approximation signal is constructed from 15 coefficients of type $float$ which, in the sensor platform, are equivalent to 30 integers. The compression ratio achieved here is thus $89.6\%$.}
		\label{figure:fouriermse}
		\end{center}
\end{figure*}


FFT is an attractive choice for two reasons. Firstly, it moslty uses integer operations and therefore is easier to
compute in resource-constrained nodes where typically a dedicated floating point hardware is absent. Secondly, it allows us
to use the Fourier coefficients, instead of the raw time-series data, to speed up the evaluation of the correlation coefficient between two time series\footnote{This is a consequense of the discrete correlation theorem \cite{openheim}.}, which we heavily utilize in our algorithms below. \eat{
\begin{center}
$Corr(g,h)_j\Longleftrightarrow G_{k}H^{\star}_{k}$
\end{center}
}
However, it must be noted that other signal compression techniques could be used instead in scenarios where processing power is not a limited resource.

\subsubsection{Fourier-based Compression (FC)}

This is the strawman algorithm that uses FFT for in-network compression. It propagates the Fourier coefficients that constitute the compressed version of a node's time series on the shortest path to the closest gateway. Say that nodes are requested to send traffic information at the end of each day with a certain error threshold $\epsilon$. Then each node identifies the least number of Fourier coefficients $k$ that can be used to reconstruct the time series with a maximum absolute error less than $\epsilon$. It sends them to the closest gateway without performing any further reduction in the way\eat{, and temporarily stores them in local memory for fault-tolerance reasons}. The FC algorithm compresses a single time series at the node where it is generated, without exploiting its similarity with previous time series generated in the same or different nodes.

%This ensures that the node shares the gateway's knowledge over a specified time window of $w$ days. 


To explore opportunities for further compression, we measured i) the correlation between two time series of the same node on different dates; and ii) the correlation between two time series of different nodes on the same date. In both cases, we used the Pearson correlation coefficient $F=[f_1, f_2,\ldots,]$ and $F'=[f_1', f_2',\ldots,]$:
\[ r (F,F') = \sqrt{cov(F,F')^2 / (var(F)\times var(F'))} \]

\subsubsection{Fourier Compression and Temporal Correlations (FC-Temporal)}


\begin{figure*}[b]	
\begin{center}
		\epsfig{file=dwg/correlation-monday.eps, height=1.8in}
		\caption{Correlation coefficient between the 31st day and every other day in May.}
		\label{figure:tempcor}
\end{center}
\end{figure*}
We observed very strong \emph{temporal correlations} in a single flow time series. For example, Figure~\ref{figure:tempcor} shows that a very high correlation coefficient ($\geq{}0.98$) is observed between the time series of a node on Wednesday, 31st of May 2006, and any other day in May, except for weekends and May 1st, which is a bank holiday in the UK. Figure~\ref{figure:percor} summarizes the extent of temporal correlations in the traffic dataset. It shows the percentage of nodes that exhibit a given correlation coefficient between today's time-series and the time-series of a previous day within the last week. For example, for more than 80\% of the sensors, their daily readings are highly correlated ($cc\geq{}0.8$) with those in one of the previous seven days. These results demonstrate the strength of temporal correlations in traffic data, and reveal the opportunity for exploiting these correlations to achieve communication savings. 

\begin{figure*}[htbp]	
\begin{center}
		\epsfig{file=dwg/percentage-vs-cf.eps, height=1.8in}
		\caption{Percentage of nodes with a given correlation coefficient between the current day and a previous day within the last week.}
		\label{figure:percor}	
\end{center}
\end{figure*}

The proposed algorithm, FC-Temporal, extends the FC algorithm, in that it exploits temporal correlations to reduce the cost of time series propagation. Each sensor node running FC-Temporal tries to compress today's time series locally, by expressing it as a linear function of a previous day's time series.

More specifically, on the first day, each node computes $k$ Fourier coefficients that can be used to reconstruct the original time series within the input error threshold $\epsilon$, as in the case of the FC algorithm. On any of the following days, say day $cur$, the node iterates through the previous approximated time series $\{\hat{f}_{cur-w},\ldots,\hat{f}_{cur-1}\}$, which are stored locally, and computes the correlation coefficient between them and the current time series $cc (f_{cur},\hat{f}_{d})$, $\forall d \in [cur-w,cur-1]$. As soon as it identifies a strongly correlated time series, say of day $pr$, it evaluates the regression parameters of the linear function that approximates $cur$'s time series based on $pr$'s readings: $\hat{f}_{cur}\left[j\right]=r_{1}+r_{2}\cdot\hat{f}_{pr}\left[j\right]$, where $j$ ranges over all readings of a day's time series. If the maximum absolute error between the approximated and the original time series on day $cur$ does not exceed the user threshold $\epsilon$, the node sends to the gateway only the regression parameters of the linear fit: If $\underset{j}{\max}\left|\hat{f}_{cur}\left[j\right]-f_{cur}\left[j\right]\right|<\epsilon$, send $\left(pr,r_{1},r_{2}\right)$ to the gateway.  When the gateway receives such a triplet, it retrieves $\hat{f}_{pr}$ from its cache, and estimates the current day's time series as $r_{1}+r_{2}\cdot\hat{f}_{pr}$ with adequate accuracy. If no linear correlation with a previous day is detected (within a window of $w$ days), the sensor node approximates and forwards today's time series independently of previous days as in FC. Figure~\ref{figure:fctemporaldesc} shows an example run of the algorithm.




\begin{figure*}[htbp]
\begin{center}
	\epsfig{file=dwg/fctemporaldesc.eps, height=1.8in}
	\caption{The FC-Temporal algorthm. A high correlation is found between the current day and previous Friday, so the node only forwards the regression paramters $a,b$ and an identifier for the corresponding day, $F$ to the gateway.}
	\label{figure:fctemporaldesc}
\end{center}
\end{figure*}

The FC-temporal algorithm requires that each node stores locally the approximate time series detected in the previous $w$ days. This is realistic since, for traffic data, very strong correlations occur by setting $w=7$. This algorithm is similar to FC, in that in-network computation occurs where data is first generated, and the algorithm does not try to merge data generated by different sensors to achieve further communication savings. 


\subsubsection{Fourier Compression and Spatial Correlations (FC-Spatial)}
We have also examined whether we can equally rely on spatial correlations between flow time series from different sensors, and whether the strength of spatial correlations depends on the physical distance between them. In order to determine whether two time series $F$ and $F'$ generated by sensors $SID$ and $SID'$ respectively are correlated, we allow a time-shift between the time series. For example if sensors $SID$ and $SID'$ are located along the same road and if the traffic flows from $SID$ to $SID'$, we expect that $f_t=f_{t+dt}'$.\footnote{Shifted correlations can be computed efficiently for all possible time-shifts $dt$ using the Fourier transform of the time series $(u)_t$ and $(v)_t$.} Figure~\ref{figure:cf-proximity} shows that the correlation coefficient between two nodes does not depend on their distance. Unlike other applications, like temperature monitoring systems, many pairs of remotely placed nodes were found to be highly correlated, whereas many pairs of nearby nodes exhibited little correlation. This is because traffic on main road arteries exhibits little variations throughout their length, and those traverse our deployment map from end to end.

\begin{figure*}[htbp]
\begin{center}
	\epsfig{file=dwg/cf-proximity.eps, height=1.8in}
	\caption{Spatial correlation between two nodes as a function of their distance. Nodes very far apart can exhibit high correlation values.}
	\label{figure:cf-proximity}
\end{center}
\end{figure*}





We propose a fully-distributed algorithm, named FC-Spatial, in order to exploit the spatial correlations observed. Each intermediate node in the communication tree receives approximated time series from its descendant nodes, and tries to further reduce them by exploiting their correlations. 

Let an intermediate node $I$ receive an approximate time series $\hat{f}(N)$ of today's traffic monitored by node $N$. This information is sent from $N$ to $I$ in the form of Fourier coefficients annotated with the Fourier compression error $\epsilon(N)$. Node $I$ searches its local memory for correlated time series and it takes one of the following steps:

\emph{Step A:} Suppose that the local cache includes another time-series $\hat{f}(M)$ of today's traffic monitored by node $M$, such that $\hat{f}(N) \approx r_1+r_2 \times \hat{f}(M)$ with regression error $\epsilon '(N)$. If the combined error of Fourier compression and linear regression $(\epsilon(N) + \epsilon '(N))$ does not exceed the user-defined threshold $\epsilon$, then node $I$ compresses $\hat{f}(N)$ into tuple $(N,M,r_1,r_2)$ before forwarding it to the gateway. When the gateway receives this tuple it can approximate the time series of $N$ based on $\hat{f}(M)$ with sufficient accuracy. To ensure that $\hat{f}(M)$ arrives at the gateway node intact, we update its entry in the cache of node $I$ with a read-only flag. When node $I$ finishes processing incoming traffic and forwards cached entries to the gateway, the read-only flag of $\hat{f}(M)$ prevents it from being modified at intermediate nodes.

\emph{Step B:} If $\hat{f}(N)$ cannot be approximated as a linear function of another node's time series, $(\hat{f}(N),\epsilon(N))$ is cached in local memory. Node $I$ forwards cached tuples to its parent, once it has finished processing incoming traffic.   

\begin{figure*}[htbp]
\begin{center}
	\epsfig{file=dwg/fcspatialdesc.eps, height=1.8in}
	\caption{FC-Spatial: Node $c$ receives approximations from nodes $a,b$ and computes their correlation. It then only forwards one of the approximations, $f_a$ and linear regression parameters for the second one ($rp_b$). }
	\label{figure:fcspatialdesc}
\end{center}
\end{figure*}



\section{Evaluation}

We have evaluated the performance of FC, FC-temporal and FC-spatial using the real traffic dataset from the city f Cambridge. In our simulations, we placed sensor nodes as in the Cambridge deployment and added a number of relay nodes to bridge disconnected network components. Relay nodes have the same capabilites as sensor nodes except sensing. FC-spatial also runs on relay nodes. We set the communication range to 250m, and carefully placed gateway nodes to minimize the sum of hop counts from sensor nodes to the closest gateway. We then measured the communication cost of the three algorithms as we vary i) the user-defined error threshold and ii) the number of gateway nodes.

Figure~\ref{figure:cost1gw} shows the total communication cost of FC, FC-Temporal and FC-Spatial in the simple scenario where we have only one gateway in the middle of the network. If data was propagated in an uncompressed form, it would generate 32.3 MBytes of traffic. If the error tolerance is increased from 5 to 15 cars per 5 minutes, Fourier Compression (FC) yields communication savings that range from 44\% to 90\%. FC-temporal is 14\%-30\% more efficient than FC for tolerated errors of 5-15 cars per 5-min interval. Similarly, FC-spatial outperforms FC by 10\%-35\% for the same error range. 

\begin{figure}[h]
\begin{center}
		\epsfig{file=dwg/total-one-gateway_.eps, height=1.8in}
		\caption{Comparison of the total communication cost incurred by the three proposed algorithms using a single gateway. The cost of propagating the traffic data in an uncompressed form is 32.3 MBytes.}
		\label{figure:cost1gw}
\end{center}
\end{figure}

Figure~\ref{figure:costvsgateways} shows the effect of adding more gateway nodes on the total communication cost, assuming a fixed error threshold of $10$ cars. We investigated the impact of various gateway placement strategies on the performance of our algorithms and decided to use the strategy that minimizes the total sum of hop counts throughout our evaluation, as this scheme proved to be the best all-round performer. The use of more gateway nodes results in better load balancing, and improves the performance of all three algorithms. This is anticipated since the more the gateway nodes, the shorter the paths that packets traverse to reach a gateway. FC-Temporal continues to yield significant communication savings compared to FC as we increase the number of gateways. However, the savings of FC-spatial diminish in networks with more than two gateways. As messages travel fewer hops to the gateway, they get fewer opportunities to be compressed along the way based on spatial correlations. \eat{Cost benefits are observed not only in the entire network, but also in the critical area around the gateways (Figure~\ref{figure:gwcostvsgateways}).}

\begin{figure}[h]
\begin{center}
		\epsfig{file=dwg/total-many-gateways_.eps, height=1.8in}
		\caption{Effect of varying the number of gateways on the communication savings of the proposed algorithms.}
		\label{figure:costvsgateways}
\end{center}
\end{figure}

\section{Discussion}

In this chapter we have presented a communication-efficient approach to extracting traffic data periodically from a sensor network. Our approach is tailored to temporary sensor deployments that acquire data for future planning applications used by authorities. Fourier-based lossy compression implemented locally at the sensor nodes was shown to offer 44-90\% savings in communication for tolerated car-flow errors of 5-15 cars per 5-min interval. Real traffic data obtained from sensors in the city of Cambridge were shown to exhibit significant temporal and spatial correlations that differ from correlations typically observed in temperature monitoring applications. Our two proposed algorithms, FC-temporal and FC-spatial, exploit such correlations to achieve significant benefits compared to Fourier compression alone. FC-temporal is 14\%-30\% more efficient than FC for tolerated errors of 5-15 cars per 5-min interval, whilst FC-spatial outperforms FC by 10\%-35\% for the same error range. Both algorithms are fully distributed and easy to implement in resource-constrained sensor and relay nodes. Increasing the number of gateways provides further communication savings but also reduces the opportunities for spatial correlations and thus the extra gains of FC-spatial.
 
